package review;

import com.sun.jmx.remote.internal.RMIExporter;

import java.util.Arrays;

/**
 * @author 郝文雪
 * @date 2022/8/3 10:29
 * @Description Test
 */
public class mergeSort {
    /**
     * 归并排序(递归)
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length-1);
    }

    private static void mergeSortInternal(int[] arr, int low, int high) {
        if(low>=high) return;
        int mid=(high-low)/2+low;
        mergeSortInternal(arr,low,mid);
        mergeSortInternal(arr,mid+1,high);
        merge(arr,low,mid,high);
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int[] tmp=new int[high-low+1];
        int k=0;
        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;
        while(s1<=e1 && s2<=e2){
            if(arr[s1]<=arr[s2]){
                tmp[k++]=arr[s1++];
            }else{
                tmp[k++]=arr[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++]=arr[s1++];
        }
        while(s2<=e2){
            tmp[k++]=arr[s2++];
        }
        for(int i=0;i< tmp.length;i++){
            arr[i+low]=tmp[i];
        }
    }

    /**
     * 归并排序（非递归）
     */
    public static void mergeSort2(int[] arr){
        for(int sz=1;sz<=arr.length;sz=sz*2){
            for(int i=0;i+sz<=arr.length;i+=sz*2){
                merge(arr,i,i+sz-1,Math.min(i+2*sz-1,arr.length-1));
            }
        }
    }


    /**
     * 合并两个有序数组
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] mergeArray(int[] arr1,int[] arr2){
        int[] tmp=new int[arr1.length+ arr2.length];
        int s1=0;
        int e1=arr1.length-1;
        int s2=0;
        int e2= arr2.length-1;
        int k=0;
        while(s1<=e1 && s2<=e2){
            if(arr1[s1]<=arr2[s2]){
                tmp[k++]=arr1[s1++];
            }else{
                tmp[k++]=arr2[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++]=arr1[s1++];
        }
        while(s2<=e2){
            tmp[k++]=arr2[s2++];
        }
        return tmp;
    }

    public static void main(String[] args) {
//        int[] arr1={1,3,4};
//        int[] arr2={2,3,5};
//        int[] arr3 = mergeArray(arr1, arr2);
        int[] arr={2,1,3,6,4,5,7};
        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));

    }
}
